package com.czk.algorithm.dynamic.bag;

/**
 * 动态规划，背包问题的复习
 *
 * @Author:ChenZhangKun
 * @Date: 2021/5/31 22:29
 */
public class BagPractice {
    public static void main(String[] args) {
        // 物品的重量数组
        int[] weight = {1, 2, 3};
        // 价值数组
        int[] value = {1500, 2000, 3000};
        // 背包容量
        int bagSpace = 4;
        // 物品的数量
        int count = weight.length;
        // 创建dp数组
        int[][] dp = new int[count + 1][bagSpace + 1];
        // 初始化第一行和第一列
        // 初始化第一列
        for (int i = 0; i < count + 1; i++) {
            dp[i][0] = 0;
        }
        // 遍历数组
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                // 此时背包的大小有1,2,3,4动态变化
                if (weight[i - 1] > j) {
                    // 此时放不进去，直接就是上一个放的值
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 比背包小
                    // 直接放入背包，看有没有剩余空间
                    // j-weight为剩余空间的列
                    // i-1为剩余空间所在的上一行，此时已经是该剩余容量的最大值
                    dp[i][j] = Math.max(dp[i - 1][j], value[i - 1] + dp[i - 1][j - weight[i - 1]]);
                }
            }
        }
        System.out.println(dp[count][bagSpace]);

    }
}
